class Solution91 {

    public static void main(String[] args) {
        System.out.println(numDecodings("12"));
    }
    public static int numDecodings(String s) {
        if(s.length() <= 1 && s.charAt(0) == '0') return 0 ; 

        s = "0" + s ;
        int n = s.length() ;

        // 1. 状态表示 , [0 , i] 区间 有多少解法
         int[] dp = new int[n] ;
         dp[0] = 1 ; dp[1] = 1 ; 
         for(int i=2 ; i < n ; i ++){
           char ret = s.charAt(i) ; 
           // 第i个不会前一个组合在一起
           if(ret != '0'){
             dp[i] += dp[i-1] ;
           }
           // 第i个和前一个组合在一起
             char prev = s.charAt(i-1) ;
             int sum = (ret-'0') + (prev -'0')*10 ;
             // 组合条件 : 1<= sum <= 26 并且前一个数字不是0
             if(1 <= sum && sum <= 26 && prev != '0' ){
            dp[i] += dp[i-2] ;
           }
            if(dp[i] == 0){
                return 0 ; 
            }
         }
        return dp[n-1] ;

    }
}